#include <bits/stdc++.h>

//#pragma GCC optimize(2)
#define For(x, y, z) for (int x = y; x <= z; ++x)
#define Rof(x, y, z) for (int x = y; x >= z; --x)
#define Eor(u) for (int i = head[u]; i; i = nxt[i])
#define SZ(x) (int(x.size()))
#define pb push_back

using namespace std;
using i64 = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

char buf[(1<<21)+5],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

inline int read() {
	int x = 0, f = 0; char ch = getchar();
	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	return f ? -x : x;
}
int __stk[128], __tp;
inline void put(i64 x) {
	if (x < 0) putchar('-'), x = -x;
	do { __stk[++__tp] = x % 10, x /= 10; } while (x);
	while (__tp) putchar(__stk[__tp--] + '0');
}

const int mod = 998244353;
inline int ksm(int x, int y, int res = 1) {
	for ( ; y; y >>= 1, x = 1ll * x * x % mod)
		(y & 1) && (res = 1ll * res * x % mod);
	return res;
}
inline int inv(int x) { return ksm(x, mod - 2); }
inline int gcd(int a, int b) { if (b) while ((a %= b) && (b %= a)); return a | b; }
inline void add(int &x, int y) { (x += y) >= mod && (x -= mod); }
inline void Min(int &x, int y) { (y < x) && (x = y); }
inline void Max(int &x, int y) { (y > x) && (x = y); }

const int N = 1e5 + 100;

int n, k, Q, a[N], b[N], len;
vector<int> ve[N];


#define ls (x << 1)
#define rs (x << 1 | 1)
#define mid ((l + r) >> 1)

struct SEG1 {
	i64 t[N << 2], tag[N << 2];
	void update(int x, int le, i64 v) { if (x) t[x] += le * v, tag[x] += v; }
	void pushdown(int x, int l, int r) { update(ls, mid - l + 1, tag[x]), update(rs, r - mid, tag[x]), tag[x] = 0; }

	void modify(int L, int R, int v, int x = 1, int l = 0, int r = n + 1) {
		if (L > R) return;
		if (l >= L && r <= R) return update(x, r - l + 1, v);
		pushdown(x, l, r);
		if (mid >= L) modify(L, R, v, ls, l, mid);
		if (mid < R) modify(L, R, v, rs, mid + 1, r);
		t[x] = t[ls] + t[rs];
	}
	void change(int p, int v, int x = 1, int l = 0, int r = n + 1) {
		if (l == r) return t[x] = v, void();
		pushdown(x, l, r);
		if (mid >= p) change(p, v, ls, l, mid);
		else change(p, v, rs, mid + 1, r);
		t[x] = t[ls] + t[rs];
	}
	i64 ask(int L, int R, int x = 1, int l = 0, int r = n + 1) {
		if (L > R) return 0; 
		if (l >= L && r <= R) return t[x];
		i64 res = 0; pushdown(x, l, r);
		if (mid >= L) res += ask(L, R, ls, l, mid);
		if (mid < R) res += ask(L, R, rs, mid + 1, r);
		return res; 
	}
}Tl, Tr, Ts;


struct SEG2 {
	int t[N << 2];

	void build(int x = 1, int l = 0, int r = n + 1) {
		if (l == r) return t[x] = a[l], void();
		build(ls, l, mid), build(rs, mid + 1, r);
		t[x] = max(t[ls], t[rs]);
	}
	void modify(int p, int v, int x = 1, int l = 0, int r = n + 1) {
		if (l == r) return t[x] = v, void();
		if (mid >= p) modify(p, v, ls, l, mid);
		else modify(p, v, rs, mid + 1, r);
		t[x] = max(t[ls], t[rs]);
	}
	int ask(int L, int R, int x = 1, int l = 0, int r = n + 1) {
		if (L > R) return 0;  ; int res = 0;
		if (l >= L && r <= R) return t[x];
		if (mid >= L) res = max(res, ask(L, R, ls, l, mid));
		if (mid < R) res = max(res, ask(L, R, rs, mid + 1, r));
		return res;
	}
	int askr(int L, int R, int v, int x = 1, int l = 0, int r = n + 1) {
		if (t[x] <= v || L > R) return 0;
		if (l >= L && r <= R) {
			if (l == r) return l;
			if (t[rs] > v) return askr(L, R, v, rs, mid + 1, r);
			return askr(L, R, v, ls, l, mid);
		} int res = 0;
		if (mid < R) res = askr(L, R, v, rs, mid + 1, r);
		if (!res && mid >= L) res = askr(L, R, v, ls, l, mid);
		return res;
	}

	int askl(int L, int R, int v, int x = 1, int l = 0, int r = n + 1) {
		if (t[x] <= v || L > R) return 0;
		if (l >= L && r <= R) {
			if (l == r) return l;
			if (t[ls] > v) return askl(L, R, v, ls, l, mid);
			return askl(L, R, v, rs, mid + 1, r);
		} int res = 0;
		if (mid >= L) res = askl(L, R, v, ls, l, mid);
		if (!res && mid < R) res = askl(L, R, v, rs, mid + 1, r);
		return res;
	}
}Tw;

#undef ls
#undef rs
#undef mid


void out() {
	cout << "Error:\n";
	For(i, 1, len) {
		cout << i <<":";
		for (int x : ve[i]) cout << x <<" ";
		cout<<'\n';
	}
}

signed main() {
	freopen("summer.in", "r", stdin);
	freopen("summer.out", "w", stdout);

    n = read(), k = read();     For(i, 1, n) a[i] = b[i] = read();
	sort(b + 1, b + n + 1),len = unique(b + 1, b + n + 1) - b - 1;
	For(i, 1, n) a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;
	a[0] = a[n + 1] = len + 1; For(i, 1, n) ve[a[i]].push_back(i);
	
	Tw.build(); For(i, 1, n) For(j, 1, SZ(ve[i]) - 1) 
	if (Tw.ask(ve[i][j - 1] + 1, ve[i][j] - 1) < i)  
	Ts.modify(ve[i][j - 1] + 1, ve[i][j] - 1, 1);

	Tl.change(0, -1), Tr.change(n + 1, -1);

	For(i, 1, n) { int p = Tw.askr(0, i - 1, a[i]);     Tl.change(i, Tl.ask(p, p) + 1); }
	Rof(i, n, 1) { int p = Tw.askl(i + 1, n + 1, a[i]); Tr.change(i, Tr.ask(p, p) + 1); }

    Q = read(); while (Q--) { 
		int x = read(), l = read(), r = read(), p = 0;
		if (a[x] == a[x + 1]) {
			put((Tl.ask(l, r) + Tr.ask(l, r) - Ts.ask(l, r)) * k + (r - l + 1) * (n - 1ll));
			putchar('\n'); continue;
		}

		int ls = Tw.askr(0, x - 1, min(a[x], a[x + 1]) - 1);
		int rs = Tw.askl(x + 2, n + 1, min(a[x], a[x + 1]) - 1);

		if (a[x] < a[x + 1]) Tl.modify(x + 2, rs - 1, 1), Tr.modify(ls + 1, x - 1, -1);
		else Tl.modify(x + 2, rs - 1, -1), Tr.modify(ls + 1, x - 1, 1);


		p = lower_bound(ve[a[x]].begin(), ve[a[x]].end(), x) - ve[a[x]].begin();
		if (p) {
			if (Tw.ask(ve[a[x]][p - 1] + 1, x - 1) < a[x])  
				Ts.modify(ve[a[x]][p - 1] + 1, x - 1, -1);
		}  
		if (p != SZ(ve[a[x]]) - 1) {
			if (Tw.ask(x + 1, ve[a[x]][p + 1] - 1) < a[x])  
				Ts.modify(x + 1, ve[a[x]][p + 1] - 1, -1);
		}
		++ve[a[x]][p];


		p = lower_bound(ve[a[x + 1]].begin(), ve[a[x + 1]].end(), x + 1) - ve[a[x + 1]].begin();
		if (p) {
			if (Tw.ask(ve[a[x + 1]][p - 1] + 1, x) < a[x + 1])  
				Ts.modify(ve[a[x + 1]][p - 1] + 1, x, -1);
		}  
		if (p != SZ(ve[a[x + 1]]) - 1) {
			if (Tw.ask(x + 2, ve[a[x + 1]][p + 1] - 1) < a[x + 1])  
				Ts.modify(x + 2, ve[a[x + 1]][p + 1] - 1, -1);
		}
		--ve[a[x + 1]][p];


		Tw.modify(x, a[x + 1]), Tw.modify(x + 1, a[x]), swap(a[x], a[x + 1]);

		p = lower_bound(ve[a[x]].begin(), ve[a[x]].end(), x) - ve[a[x]].begin();
		if (p) {
			if (Tw.ask(ve[a[x]][p - 1] + 1, x - 1) < a[x])  
				Ts.modify(ve[a[x]][p - 1] + 1, x - 1, 1);
		}  
		if (p != SZ(ve[a[x]]) - 1) {
			if (Tw.ask(x + 1, ve[a[x]][p + 1] - 1) < a[x])  
				Ts.modify(x + 1, ve[a[x]][p + 1] - 1, 1);
		}

		p = lower_bound(ve[a[x + 1]].begin(), ve[a[x + 1]].end(), x + 1) - ve[a[x + 1]].begin();
		if (p) {
			if (Tw.ask(ve[a[x + 1]][p - 1] + 1, x) < a[x + 1])  
				Ts.modify(ve[a[x + 1]][p - 1] + 1, x, 1);
		}  
		if (p != SZ(ve[a[x + 1]]) - 1) {
			if (Tw.ask(x + 2, ve[a[x + 1]][p + 1] - 1) < a[x + 1])  
				Ts.modify(x + 2, ve[a[x + 1]][p + 1] - 1, 1);
		}

		p = Tw.askr(0, x - 1, a[x]), Tl.change(x, Tl.ask(p, p) + 1);
		p = Tw.askr(0, x, a[x + 1]), Tl.change(x + 1, Tl.ask(p, p) + 1);

		p = Tw.askl(x + 2, n + 1, a[x + 1]), Tr.change(x + 1, Tr.ask(p, p) + 1);
		p = Tw.askl(x + 1, n + 1, a[x]), Tr.change(x, Tr.ask(p, p) + 1);

		put((Tl.ask(l, r) + Tr.ask(l, r) - Ts.ask(l, r)) * k + (r - l + 1) * (n - 1ll)), putchar('\n');
    }
	// cerr << clock() / 1000.0<<'\n';
	return 0;
}